package com.dycong.common.leetcode.yi;

import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-07-16
 * Time: 17:46
 */
public class LruCache {
    private int capacity;
    private LinkNode first;
    private LinkNode last;
    private HashMap<Integer, LinkNode> cache;

    public static void main(String[] args) {
        LruCache lruCache = new LruCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }

    public LruCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<Integer, LinkNode>(capacity);
    }

    public int get(int key) {
        LinkNode res = cache.get(key);
        if (res == null) return -1;
        moveNodeToFirst(res);
        return res.val;
    }

    public void put(int key, int value) {
        LinkNode temp = cache.get(key);
        if (temp == null) {
            if (cache.size() >= capacity) {
                removeLastNode();
            }
            temp = new LinkNode();
            temp.key = key;
        }
        temp.val = value;
        moveNodeToFirst(temp);
        cache.put(key, temp);
    }

    private void removeLastNode() {
        LinkNode temp = last;
        last = last.pre;
        if (last != null) {
            last.next = null;
        } else {
            first = last = null;
        }

        cache.remove(temp.key);

    }

    private void moveNodeToFirst(LinkNode node) {
        if (first == node) return;
        if (node.pre != null) {
            node.pre.next = node.next;
        }
        if (node == last) {
            last = last.pre;
        }
        if (last == null) {
            first = last = node;
            return;
        }

        node.next = first;
        first.pre = node;
        first = node;
        node.pre = null;
    }

    class LinkNode {
        LinkNode pre;
        LinkNode next;
        int key;
        int val;
    }
}
